1510I - Is It Rated - CodeForces Solution

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

#define fopen                                   \
    freopen("E:/vscode/oi/in.txt", "r", stdin); \
    freopen("E:/vscode/oi/out.txt", "w", stdout);
#define fc         \
    fclose(stdin); \
    fclose(stdout);
#define ios                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);

#define i64 long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define ld long double
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) (x & -x)
#define de(x) cout << #x << " = " << x << '\n'
#define MAXP 20

#define int i64

const int N = 1e3 + 10, M = 4e5 + 10, mod = 1e6;
const double eps = 1e-12, base = 0.5;
const double PI = acos(-1);

char s[N], ans, res;
int wa[N];

random_device rd;
mt19937 rnd(rd());

char check()
{
    cout << res << '\n';
    cout.flush();
    char c;
    cin >> c;
    return c;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    int tot = 0, delta = 0;
    while (m--)
    {
        cin >> s + 1;
        double c0, c1;
        c0 = c1 = 0;
        for (int i = 1; i <= n; i++)
            if (s[i] == '0')
                c0 += powl(base, wa[i] - delta);
            else
                c1 += powl(base, wa[i] - delta);

        double p = rnd() % mod / 1.0 / mod;
        // de(p);
        if (p <= c0 / (c0 + c1))
            res = '0';
        else
            res = '1';
        ans = check();
        delta = mod;
        for (int i = 1; i <= n; i++)
            wa[i] += (s[i] != ans), delta = min(delta, wa[i]);
        tot += (res != ans);
    }
    // de(tot);
}

signed main()
{
    // ios;
    // fopen;
    auto st_time = high_resolution_clock::now();

    int t = 1;
    srand(time(0));

    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve();
    }

    // 获取当前时间点
    auto ed_time = high_resolution_clock::now();

    // 计算运行时间（毫秒为单位）
    auto duration = duration_cast<milliseconds>(ed_time - st_time);

    // 打印运行时间
    // cout << "运行时间：" << duration.count() << " 毫秒" << '\n';

    return 0;
}